The present invention relates to public key cryptography, and more particularly to digital certificate revocation.
Digital certificates 104 (FIG. 1) are used in public key infrastructures (PKI) to facilitate secure use and management of public keys in a networked computer environment. Users U1, U2, . . . utilize their computer systems 110.1, 110.2, . . . to generate respective key pairs (PK, SK) where PK is the public key and SK is the secret key. FIG. 1 shows a key pair (PKU1, SKU1) for user U1. The users register their public keys PK, over a network, with a certification authority (CA) 120. Alternatively, the key pairs can be generated by CA 120 and sent to the users. CA 120 is a secure, trusted computer system. For each public key PK, CA 120 generates a digital certificate 104. Certificate 104 contains the public key PK and the user's name and may also contain the user's email address or addresses, the certificate's serial number SN (generated by the CA to simplify the certificate management), the certificate issue date D1, the expiration date D2, an identification of algorithms to be used with the public and secret keys, an identification of the CA 120, and possibly other data. The data mentioned above is shown at 104D. Certificate 104 also contains CA's signature 104-SigCA on the data 104D. The signature is generated using CA's secret key SKCA. CA 120 sends the certificate 104 to the user's (key owner's) computer system 110. Either the owner or the CA 120 can distribute the certificate to other parties to inform them of the user's public key PK. Such parties can verify the CA's signature 104-SigCA with the CA's public key PKCA to ascertain that the certificate's public key PK does indeed belong to the person whose name and email address are provided in the certificate.
A certificate may have to be revoked prior to its expiration date D2. For example, the certificate owner U may change his affiliation or position, or the owner's private key SKU may be compromised. Other parties must be prevented from using the owner's public key if the certificate is revoked.
One approach to prevent the use of public keys of revoked certificates is through a certificate revocation list (CRL). A CRL is a signed and time-stamped list issued by CA 120 and specifying the revoked certificates by their serial numbers SN. These CRLs must be distributed periodically even if there are no new revoked certificates in order to prevent any type of replay attack. The CRL management may be unwieldy with respect to communication, search, and verification costs. Certificate revocation trees (CRTs) can be used instead of CRLs as described in [15] (the bracketed numbers indicate references listed at the end before the claims).
Instead of CRLs and CRTs, CA 120 could answer queries about specific certificates. In FIG. 1, user U2 issues a query 150 with the serial number SN of certificate 104 of user U1. CA 120 responds with a validity status information 160 containing the serial number SN, a validity status field 160VS (“valid”, “revoked” or “unknown”), and a time stamp “Time”. The response is signed by CA (field 160-SigCA). This approach is used for Online Certificate Status Protocol (OCSP). See [23]. Disadvantageously, the CA's digital signature 160-SigCA can be quite long (over 1024 bits with RSA), especially since the CA must be very secure. In addition, if CA 120 is centralized, the CA becomes a validation bottleneck. If CA 120 is decentralized (replicated), the security is weakened as the CA's signing key SKCA is replicated.
FIG. 2 illustrates a “NOVOMODO” approach, which allows CA 120 to provide an unsigned validity status through untrusted directories 210 at pre-specified time intervals (e.g. every day, or every hour, etc.). Directories 210 are computer systems that do not store secret information. The system works as follows.
Let f be a predefined public length-preserving function
f: {0,1}n→{0,1}n 
where {0,1}n is the set of all binary strings of a length n. Let fi denote the f-fold composition; that is, fi(x)=x for i=0, and fi(x)=fi(fi-1(x)) for i>0. Let f be one-way, i.e. given f(x) where x is randomly chosen, it is hard (infeasible) to find a pre-image z such that f(z)=f(x), except with negligible probability. “Infeasible” means that given a security parameter k (e.g. k=n), the pre-image z cannot be computed in a time equal to a predefined polynomial in k except with negligible probability. Let us assume moreover that f is one-way on its iterates, i.e. for any i, given y=fi(x), it is infeasible to find z such that f(z)=y.
We can assume, without loss of generality, that CA is required to provide a fresh validity status every day, and the certificates are valid for one year, i.e. 365 days (D2−D1=365 days). To create a certificate 104 (FIG. 2), CA 120 picks a random “seed” number x and generates a “hash chain” c0, c1, . . . c365 wherein:c365=f(x),c364=f(f(x)), . . . c1=f365(x), c0=f366(x).  (1)We will sometimes denote x as x(SN) for a certificate with a serial number SN, and similarly ci=ci(SN) where i=0, 1, . . . . The value c0 is called a “validation target”. CA 120 inserts c0 into the certificate 104 together with data 104D (FIG. 1). CA 120 also generates a random revocation seed number N0, computes the “revocation target” N1=f(N0), and inserts N1 into certificate 104. CA 120 keeps all ci secret for i>0. The values x and N0 are also secret. Clearly, all ci can all be computed from x, and the validation target c0 can be computed from any ci. CA 120 stores in its private storage the values x and N0 for each certificate 104, and possibly (but not necessarily) caches the ci values.
Every day i (i=1, 2, . . . 365), for each certificate 104, CA distributes to directories 210 a validity proof data structure which includes, in addition to a validity status indication (not shown in FIG. 2, can be “valid” or “revoked”):
1. the certificate's “i-token” ci if the certificate is valid on day i;
2. the revocation seed N0 if the certificate has been revoked.
This information is distributed unsigned. Each directory 210 provides this information, unsigned, to a requester system 110 in response to a validity status request 150 (FIG. 1). To verify, the requester (verifier) 110 performs the following operations:
1. If the validity status is “valid”, the verifier 110 checks that fi(ci)=c0.
2. If the validity status is “revoked”, the verifier 110 checks that f(N0)=N1.
Despite the validity information being unsigned, the scheme is secure because given ci, it is infeasible to compute the subsequent tokens ci+1, ci+2, . . . .
To reduce the communication between CA 120 and directories 210, a hash chain (1) can be generated for a set of certificates 104, and a single i-token ci can be distributed for the set if the set is “unrevoked” (i.e. all the certificates are unrevoked in the set). FIG. 3 illustrates certificate sets F1 through F4. F1 is the set of all the certificates 104; F2⊂F3⊂F1 and F4⊂F1. In addition to the seed numbers x, N0 for each certificate 104, CA 120 generates random seed numbers x(Fi), N0(Fi) for each set Fi and constructs a hash chain (1) from each number x(Fi), with a validation target c0(Fi)=f366(x(Fi)). Each certificate 104 is augmented with the targets c0(Fi) for each set Fi containing the certificate.
Every day i, if all the certificates are valid, CA 120 distributes to directories 210 only the i-token ci(F1). If only the set F3 has invalid certificates, CA 120 distributes the i-tokens for the set F4 and for all the valid certificates in the set F2. If only the set F2-F3 has invalid certificates, CA 120 distributes the i-tokens for the sets F3 and F4 and for all the valid certificates in F2-F3, and so on.
In response to a validity status request for a certificate 104, a directory 120 sends to the requester (the verifier):
1. an i-token ci for the certificate or for a set Fi containing the certificate if the certificate is valid;
2. the certificate's revocation number N0 if the certificate has been revoked.
If the response indicates that the certificate is valid, the verifier checks that fi(ci) is equal to one of the certificate's validation targets. If the response indicates that the certificate is revoked, the verifier checks that f(N0)=N1 for the certificate.
Clearly, for each set R of revoked certificates (FIG. 4), it is desirable to find a minimum set of sets Fi covering the valid certificates R′. By definition herein, the sets {Fi} “cover” R′ if the union U Fi=R′. We will say that {Fi} is the “complement cover” of R. The complement cover of R will be denoted as CCR.
Also, it is desirable to find a system of sets {F} containing a small complement cover for any set R or at least for many possible sets R. If {F} contains a cover for each set R of the certificates, we will call {F} a complement cover for the set of all the certificates, and will denote this complement cover CC(U) or just CC.
For uniformity, we will assume that each certificate 104 corresponds to a singleton set consisting of that certificate. The hash chain for the singleton set is the same as for the certificate.
Clearly, if {F} contains the singleton set for each certificate, then {F} is a complement cover for the set of all the certificates.
Complement covers can be constructed using trees. FIG. 5 illustrates a binary tree 510 for eight certificates, numbered 1 through 8. Each node represents a set Fi. Each leaf node (labeled 1, 2, . . . ) represents a singleton set for a respective certificate 1, 2, . . . . Each higher level node represents the union of its children. E.g., node 1-4 represents the set of certificates 1 through 4. The root represents all the certificates. (We will use the numeral 510 to represent both the tree and the complement cover.)
If a certificate is revoked, then the corresponding leaf is revoked, i.e. represents a set that cannot be used for the i-token distribution. Also, each node in the path from the leaf to the root is revoked. In the example of FIG. 6, the certificates 3 and 8 are revoked (as indicated by “x” marks). The sets 3-4, 1-4, 1-8, 7-8, 5-8 are therefore revoked. The minimal complement cover CCR of the revoked certificates consists of nodes 1-2, 4, 5-6, 7. Generally, the minimal complement cover CCR consists of all the nodes that are children of the revoked nodes. Computer tree traversal algorithms are known that can be implemented on CA 120 to mark revoked nodes when a certificate is revoked, and to find all the immediate unrevoked children of the revoked nodes. Each day CA 120 distributes the i-tokens for the immediate children and the N0 tokens for the revoked leafs.